COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00009 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A88.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 13, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
Consider a machine $M$ with an input device, a Turing memory device, and an
oracle for an arbitrary set $A$.  Let $H(u,v)$ be the predicate: $M$, with
program $u$, and with input $v$, halts.  If there were an algorithm
executable by $M$ to determine $H(u,v)$ from input $[u,v]$, the algorithm could 
be modified in an obvious way to take input $w$, construct $[w,w]$, and 
determine $H(w,w)$.  We could further modify the algorithm so that
on input $w$, it determines $H(w,w)$, enters a non-terminating part
of the program like $\langle i\rightarrow i$, $\delta$, $\delta \rangle$
if $H(w,w)$ is true, and halts if $H(w,w)$ is false.  Let $p$ be a 
program that carries out the above algorithm.

Now execute $p$, setting its input to $p$.  Then $p$ constructs $[p,p]$ and
determines $H[p,p]$, thereby predicting whether it will itself halt, given the
input that it actually has.  If it predicts that it will halt, it then runs
forever.  If it predicts that it will not halt, it immediately halts.  Either
story is self-contradictory.  The only assumption that was not justified was 
the assumption that an algorithm can determine $H(u,v)$, so this assumption
must be false.  There can be no algorithm executable by a  Turing machine with 
oracle for $A$ that determines whether a given program for that machine halts
on given data.  This theorem, called the undecidability of the halting problem, is 
true no matter what set $A$ is.

Let $A$ be any set, and $M$ a Turing machine using that oracle.  Let $A'$ be the
set of $[u,v]$ such that on machine $M$, program $u$ halts on input $v$.  Let
$M'$ be a Turing machine with oracle $A'$.  We shall see that $M'$ can compute
any partial function that $M$ can, but not conversely.

Obviously, $M'$ can solve arbitrary halting problems concerning $M$.  A program
for $M'$, given $[u,v]$, need only consult the oracle for $A'$ and report
the result.  The undecidability theorem shows that no program for $M$ can do
this.

To show that $M'$ can do whatever $M$ can do, we show that $M'$ can simulate
every step of a computation for $M$.  The only steps it can't handle in an
obvious way are those that determine whether $w\in A$.

Let $p$ be a program for $M$ that, on any input $w$, uses the oracle for
$A$ to determine whether $w\in A$, halting if $w\in A$ and diverging 
if $w\notin A$.  $M'$ can test whether $w\in A$ by testing whether $[p,w] \in A'$.

We call $A'$ the {\it jump} of $A (\hbox {or} J(A)?)$.

We can partially order oracles by their usefulness.  If a {\rm TM} with oracle 
$A↓1$ can do everything that a {\rm TM} with oracle $A↓2$ can do, we say 
$A↓1 \geq A↓2$.  If the converse is false, we say $A↓1 > A↓2$.  If
$A↓1 \geq A↓2$ and $A↓2 \geq A↓1$, we say $A↓1 \sim A↓2$.  Clearly
$A \geq A$, $A \sim A$, $A↓1 \sim A↓2 \supset A↓2 \sim A↓1$, and
$A↓1 \geq A↓2 \geq A↓3 \supset A↓1 \geq A↓3$, so $\geq$ is a weak partial
order, $>$ is a strong partial order, and $\sim$ is an equivalence relation.
Obviously $\emptyset\leq A$, and $A \sim \emptyset$ iff $A$ is a 
recursive set.  There is no 
maximal element of the partial order; we have shown that {\rm Jump}$(A) > A$.
Starting with any set $A↓0$, we can define $A↓{i+1} H $ ${\rm Jump}(A↓i)$, giving
an infinite hierarchy of increasingly powerful oracles.

For any infinite sequence of sets, $B↓i$, we can define 
$B↓\omega = \{[i,x]\mid x\in B↓i\}$; clearly $B↓\omega > B↓i$ for all $i\in N$.  
We can proceed to $B↓{\omega + 1}$, $B↓{\omega + 2}$, etc.

If $A$ is recursively enumerable, {\rm Jump}$(\emptyset ) \geq A$.  It is
known that there are sets intermediate between $\emptyset$ 
and {\rm Jump}$(\emptyset)$.  In fact, there are sets for which the partial order
is \vskip 1in
showing that the partial order is not total.
$$[?:{\tt if}\, A↓1 \geq A↓2, {\tt is\, Jump}(A↓1) \geq {\tt Jump}(A↓2)?]$$
If $r(x,y)$ is A-computable then $s(x) \equiv \exists y\mid r(x,y)$ and
$t(x) \equiv \forall y\mid r(x,y)$ are {\rm Jump(A)-computable}.  Show
that $u(x) \equiv \forall y\mid \exists z \mid r(x,y,z)$ need not be in
${\tt Jump} (A)$.
\bye